武士风度的牛
题目 武士风度的牛
思路分析
已经大成了
照着模版默 一遍过 甚至没有debug的过程
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=160;
int n,m;
char g[N][N];
int d[N][N];
int startx,starty,targetx,targety;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n-1 && y>=0 && y<=m-1 && d[x][y]==-1;
}
void bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
q.push({x,y});
d[x][y]=0;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
if(ux==targetx && uy==targety){
cout<<d[ux][uy];
return;
}
for(int i=0;i<8;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && (g[nx][ny]=='.' || g[nx][ny]=='H')){
q.push({nx,ny});
d[nx][ny]=d[ux][uy]+1;
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>m>>n;
for(int i=0;i<n;i++){
cin>>g[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='K')
startx=i,starty=j;
if(g[i][j]=='H')
targetx=i,targety=j;
}
}
bfs(startx,starty);
return 0;
}
💬 评论